/*
 * @Author: your name
 * @Date: 2024-06-12 14:08:01
 * @LastEditTime: 2024-06-12 14:14:13
 * @LastEditors: your name
 * @Description: In User Settings Edit
 * @FilePath: \.leetcode\509.斐波那契数.cpp
 */
/*
 * @lc app=leetcode.cn id=509 lang=cpp
 *
 * [509] 斐波那契数
 */

// @lc code=start
class Solution {
public:
    int fib(int n) {
        if(n <= 1){
            return n;
        }
        vector<int> dp(n+1);
        dp[0] = 0;
        dp[1] = 1;
        for(int i = 2; i <= n; i++){
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n];
    }
};
// @lc code=end

